package com.ming.learn.from.carl.doublepointer;

/*
编号：27. 移除元素
 */
public class Of20201228LeetCode27 {
    /*
    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
    不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并「原地」修改输入数组。
    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     */

    public static void main(String[] args) {
        System.out.println(removeElement(new int[]{1, 2, 3, 4, 5, 6, 6, 4, 2, 4}, 4));
    }
    /*
    暴力解法：两个for循环
    时间复杂度O(n^2)
    代码略
     */

    /*
    双指针法（快慢指针法）：「通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。」
    「双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。」
    双指针法将时间复杂度O(n^2)的解法优化为 O(n)的解法。
     */
    private static int removeElement(int[] nums, int val) {
        int slowIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==val)
                continue;
            nums[slowIndex++]=nums[i];
        }

        return slowIndex;
    }
}
